Search for: All records

A financial network is a web of contracts between firms. Each firm wants the best possible contracts. However, a contract between two firms requires the cooperation of both firms. This contest between cooperation and competition is studied in “Incentive-Aware Models of Financial Networks” by Akhil Jalan, Deepayan Chakrabarti, and Purnamrita Sarkar. They show how contract negotiations lead to a stable network where no firm wants to change contract sizes. In this network, the size of any contract depends on the beliefs of all firms, not just the contract’s two parties. Minor news about one firm can affect these beliefs, causing drastic changes in the network. Moreover, under realistic settings, a regulator cannot trace the source of such changes. This research illustrates the importance of firms’ beliefs and their implications for network stability. The insights could inform regulatory strategies and financial risk management. 

We study transfer learning for estimation in latent variable network models. In our setting, the conditional edge probability matrices given the latent variables are represented by P for the source and Q for the target. We wish to estimate Q given two kinds of data: (1) edge data from a subgraph induced by an o(1) fraction of the nodes of Q, and (2) edge data from all of P. If the source P has no relation to the target Q, the estimation error must be Ω(1). However, we show that if the latent variables are shared, then vanishing error is possible. We give an efficient algorithm that utilizes the ordering of a suitably defined graph distance. Our algorithm achieves o(1) error and does not assume a parametric form on the source or target networks. Next, for the specific case of Stochastic Block Models we prove a minimax lower bound and show that a simple algorithm achieves this rate. Finally, we empirically demonstrate our algorithm's use on real-world and simulated graph transfer problems. 

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map 𝑓 to an element sampled uniformly at random from a 𝑘-dimensional variety 𝑉. This class of sources generalizes both polynomial sources, studied by Dvir, Gabizon and Wigderson (FOCS 2007, Comput. Complex. 2009), and variety sources, studied by Dvir (CCC 2009, Comput. Complex. 2012). Assuming certain natural non-degeneracy conditions on the map 𝑓 and the variety 𝑉 , which in particular ensure that the source has enough min-entropy, we extract almost all the min-entropy of the distribution. Unlike the Dvir–Gabizon–Wigderson and Dvir results, our construction works over large enough finite fields of arbitrary characteristic. One key part of our construction is an improved deterministic rank extractor for varieties. As a by-product, we obtain explicit Noether normalization lemmas for affine varieties and affine algebras. Additionally, we generalize a construction of affine extractors with exponentially small error due to Bourgain, Dvir and Leeman (Comput. Complex. 2016) by extending it to all finite prime fields of quasipolynomial size. 

Boja\'{n}czy, Miko{\l}aj; Chekuri, Chandra